//
// Created by guanyicheng on 2022/4/28.
//

#include "../../common.h"

class Solution {
public:
    int strStr(string haystack, string needle) {
        if (haystack == needle) {
            return 0;
        }
        auto dfa = vector<vector<int>>(26, vector<int>(needle.size(), 0));
        dfa[needle[0] - 'a'][0] = 1;
        int rbStatus = 0;
        for (int j = 1; j < needle.size(); ++j) {
            for (int i = 0; i < 26; ++i) {
                dfa[i][j] = dfa[i][rbStatus];
            }
            dfa[needle[j] - 'a'][j] = j + 1;
            rbStatus = dfa[needle[j] - 'a'][rbStatus];
        }

        int i = 0, j = 0;
        for (; i < haystack.size() && j < needle.size(); ++i) {
            j = dfa[haystack[i] - 'a'][j];
        }
        if (j == needle.size()) {
            return i - j;
        }
        return -1;
    }
};

int main() {
    cout << Solution().strStr("", "");
}